package org.ww.algorithm.queue;

import java.util.Scanner;

public class Josephu {

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        System.out.println("请输入参与小孩数");
        int c = sc.nextInt();  //参与小孩数
        System.out.println("请输入从第几个孩子开始数");
        int m=sc.nextInt();     //从第几个小孩开始数
        System.out.println("请输入每数到几时小孩出圈");
        int k=sc.nextInt();

        CircleLinkedChild circleLinkedChild=new CircleLinkedChild();
        circleLinkedChild.addChild(c);
        circleLinkedChild.getChildren();
        circleLinkedChild.childOut(c,m,k);
    }

}
class CircleLinkedChild{
    Children first=null;
    //构造小孩圈：循环链表
    public void addChild(int c){
        if(c<1){
            System.out.println("输入的小孩数无意义");
            return ;
        }
        //定义一个辅助指针帮助加孩子
        Children helper=null;
        for(int i=1;i<=c;i++){
            Children next=new Children(i);
            if(i==1){
                first=next;
                helper=first;
                first.setNext(first);
            }else {
                helper.setNext(next);
                next.setNext(first);
                helper=next;
            }
        }
    }

    //输出所有小孩
    public void getChildren(){
        if(first==null){
            System.out.println("没有小孩队列");
            return;
        }
        System.out.println("小孩子：");
        Children helper=first;
        while (true){
            System.out.println(helper.getNo());
            if(helper.getNext()==first){
                break;
            }
            helper=helper.getNext();
        }
    }


    //小孩出圈
    public void childOut(int c,int m,int k){
        if(c<1){
            System.out.println("孩子异常");
            return ;
        }
        Children helper=first;
        //将帮助指针一直指向最后一个
        while (true){
            if(helper.getNext()==first){
                break;
            }
            helper=helper.getNext();
        }
        //刚开始将first和helper都指向开始的那个孩子
        for(int i=0;i<m-1;i++){
            first=first.getNext();
            helper=helper.getNext();
        }
        //出圈
        while (true){
            //剩下最后一个孩子了
            if(helper==first){
                break;
            }
            for(int i=0;i<k-1;i++){
                first=first.getNext();
                helper=helper.getNext();
            }
            System.out.println("孩子"+first.getNo()+"出圈");
            //孩子出圈
            first=first.getNext();
            helper.setNext(first);
        }
        System.out.println("最后一个小孩"+first.getNo()+"出圈了");
    }
}

class Children{
    private int no;
    private Children next;

    public Children(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public Children getNext() {
        return next;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public void setNext(Children next) {
        this.next = next;
    }
}